// https://www.lintcode.com/problem/backpack-ii/description

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @param V: Given n items with value V[i]
     * @return: The maximum value
     */
    int backPackII(int m, vector<int> &A, vector<int> &V) {
        // int n = A.size();
        // vector<vector<int>> res(n + 1, vector<int>(m + 1, INT_MIN));
        // res[0][0] = 0;
        // int maxVal = 0;
        // for (int i = 1; i < n + 1; ++i)
        // {
        //     // for (int j = A[i - 1]; j < m + 1; ++j) 会有遗漏，不一定res[i - 1][j - A[i - 1]]就是最大
        //     for (int j = 0; j < m + 1; ++j) 
        //     {
        //         res[i][j] = res[i - 1][j];
        //         if (j >= A[i - 1] && res[i - 1][j - A[i - 1]] != INT_MIN)
        //             res[i][j] = max(res[i][j], res[i - 1][j - A[i - 1]] + V[i - 1]);
        //     }
        //     // if (res[i][m] > maxVal) maxVal = res[i][m]; 错的，是i==n时候的最大
        // }
        // for (int j = 0; j < m + 1; ++j)
        //     maxVal = max(maxVal, res[n][j]);
        // return maxVal;
        
        // 打印路径
        int n = A.size();
        vector<vector<int>> res(n + 1, vector<int>(m + 1, INT_MIN));
        vector<vector<int>> recPath(n + 1, vector<int>(m + 1, 0));

        res[0][0] = 0;
        int maxVal = 0;
        for (int i = 1; i < n + 1; ++i)
        {
            // for (int j = A[i - 1]; j < m + 1; ++j) 会有遗漏，不一定res[i - 1][j - A[i - 1]]就是最大
            for (int j = 0; j < m + 1; ++j) 
            {
                res[i][j] = res[i - 1][j];
                if (j >= A[i - 1] && res[i - 1][j - A[i - 1]] != INT_MIN)
                {
                    res[i][j] = max(res[i][j], res[i - 1][j - A[i - 1]] + V[i - 1]);
                    if (res[i][j] == res[i - 1][j - A[i - 1]] + V[i - 1])
                    {
                        recPath[i][j] = 1;
                    }
                }
            }
        }
        int w = 0;
        for (int j = 0; j < m + 1; ++j)
        {
            maxVal = max(maxVal, res[n][j]);
            if (maxVal == res[n][j])
                w = j;
        }
        vector<int> selected(n);
        for (int i = n; i >= 1; --i)
        {
            if (recPath[i][w] == 1)
            {
                selected[i - 1] = true;
                w -= A[i - 1];
            }
        }
        for (int i = 0; i < n; ++ i)
        {
            if (selected[i])
            {
                cout << "Item" << i << " weight:" << A[i] <<" value:" << V[i] << endl;
            }
        }
        return maxVal;
    }
};

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param a: Given n items with size A[i]
     * @param v: Given n items with value V[i]
     * @return: The maximum value
     */
    int backPackII(int m, vector<int> &a, vector<int> &v) {
        int n = a.size();
        vector<vector<int>> rec(n + 1, vector<int>(m + 1, 0));
        rec[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = m; j >= 0; --j) {
                rec[i][j] = rec[i - 1][j];
                if (j >= a[i - 1]) {
                    rec[i][j] = max(rec[i][j], rec[i - 1][j - a[i - 1]] + v[i - 1]);
                }
            }
        }
        int maxVal = 0;
        for (int j = 0; j <= m; ++j) {
            maxVal = max(maxVal, rec[n][j]);
        }
        return maxVal;

        // 空间优化
        // vector<int> record(m + 1, 0);
        // for (int i = 0; i < A.size(); ++i)
        // {
        //     for (int j = m; j >= A[i]; --j)
        //     {
        //         record[j] = max(record[j], record[j - A[i]] + V[i]);                
        //     }
        // }
        // return record[m];
    }
};